#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        
        if (n == 0) {
            return 0;
        }

        // 表示以 nums[i] 为结尾的最长递增子序列的长度
        int f[n];
        // 表示以 nums[i] 为结尾的最长递增子序列的个数
        int count[n];

        for (int i = 0; i < n; i++) {
            // 长度的初始值为 1，因为自身可以当作递增子序列
            f[i] = 1;
            // 个数的初始值也为 1
            count[i] = 1;

            for (int j = 0; j < i; j++) {
                // 如果之前某个最长递增子序列的结尾小于当前的值
                // 那么可以将当前的值放入到这个子序列中
                if (nums[j] < nums[i]) {
                    // 比较长度，如果比当前记录的长度要长
                    // 证明找到新的以 nums[i] 为结尾的最长递增子序列
                    if (f[i] < f[j] + 1) {
                        // 这里个数就等于之前序列的个数
                        count[i] = count[j];
                        f[i] = f[j] + 1;
                    } else if (f[i] == f[j] + 1)  {
                        // 如果长度相等，证明出现了多个能到达该长度的递增子序列，个数进行累加
                        count[i] += count[j];
                    }       
                }
            }
        }

        int longest = 0;
        int ans = 0;

        // 重新再遍历一次（放到上面也可以，但是逻辑不清晰），
        // 找到最长的递增子序列，并且累计出现的次数
    
        // 这里可能会有疑问，为什么是累加？
        // 因为 count[i] 统计的只是以 nums[i] 为结尾的最长递增子序列的个数，
        // 而我们要统计所有长度为 longest 的最长递增子序列个数，
        // 长度为 longest 但是结尾不相同的最长递增子序列可能有多个，因此累加
        for (int i = 0; i < n; i++) {
            if (f[i] > longest) {
                ans = count[i];
                longest = f[i];
            } else if (f[i] == longest) {
                ans += count[i];
            }
        }

        return ans;
    }
};

int main() {
    vector<int> nums = {1,3,5,4,7};

    cout << Solution().findNumberOfLIS(nums) << endl;

    return 0;
};